//二叉树
//每个节点的键值大于左孩子
//每个节点的键值小于右孩子
//以左右孩子为根的子树仍为二分搜索树

function BinarySearchTree() {
  this.root = null
}

BinarySearchTree.prototype = {
  Node: function (key) {
    this.key = key;
    this.left = null;
    this.right = null;
  },
  //插入值
  insert: function (key) {
    var newNode = new this.Node(key);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.__insertNode(this.root, newNode)
    }
    console.log(this.root)
  },
  //插入节点
  __insertNode: function (node, newNode) {
    if (newNode.key < node.key) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.__insertNode(node.left, newNode)
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.__insertNode(node.right, newNode)
      }
    }
  },
  //查询某个节点
  searchNode: function (node, key) {
    if (node === null) {
      return false;
    }
    if (node.key < key) {
      return this.searchNode(node.right, key);
    } else if (node.key > key) {
      return this.searchNode(node.left, key)
    } else {
      return true
    }
  },
  //前序遍历,中左右
  preOrder: function () {
    this.__preOrder(this.root)
  },
  __preOrder: function (node) {
    if (node !== null) {
      console.log(node.key);
      this.__preOrder(node.left);
      this.__preOrder(node.right);
    }
  },
  //中序遍历,左中右,能够从小到大打印节点
  inOrder: function () {
    this.__inOrder(this.root)
  },
  __inOrder: function (node) {
    if (node !== null) {
      this.__inOrder(node.left);
      console.log(node.key);
      this.__inOrder(node.right);
    }
  },
  //后序遍历,左右中,先遍历子节点
  postOrder: function () {
    this.__postOrder(this.root)
  },
  __postOrder: function (node) {
    if (node !== null) {
      this.__postOrder(node.left);
      this.__postOrder(node.right);
      console.log(node.key)
    }
  },
  //层序遍历
  levelOrder: function () {
    let queue = [];
    queue.push(this.root);
    while (queue.length != 0) {
      let node = queue.shift()
      console.log(node.key);
      if (node.left) {
        queue.push(node.left)
      }
      if (node.right) {
        queue.push(node.right)
      }
    }
  },
  //查找最大值
  findMax: function () {
    return this.__findMax(this.root)
  },
  __findMax: function (node) {
    if (node.right === null) {
      return node.key
    }
    while (node.right !== null) {
      return this.__findMax(node.right)
    }
  },
  //查找最小值
  findMin: function () {
    return this.__findMin(this.root)
  },
  __findMin: function (node) {
    if (node.left === null) {
      return node.key
    }
    while (node.left !== null) {
      return this.__findMin(node.left)
    }
  },
  //删除最大值
  removeMax: function () {
    if (this.root) {
      this.root = this.__removeMax(this.root)
    }
  },
  __removeMax: function (node) {
    if (node.right === null) {
      let leftNode = node.left
      delete node
      return leftNode;
    }
    node.right = this.__removeMax(node.right)
    return node
  },
  //删除最小值
  removeMin: function () {
    if (this.root) {
      this.root = this.__removeMin(this.root)
    }
  },
  __removeMin: function (node) {
    if (node.left === null) {
      let rightNode = node.right
      delete node
      return rightNode
    }
    node.left = this.__removeMin(node.left)
    return node
  }
}

let bst = new BinarySearchTree();
bst.insert(90)
bst.insert(50)
bst.insert(60)
bst.insert(190)
bst.insert(180)
bst.insert(290)
bst.insert(20)